import java.util.Arrays;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=51 lang=java
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution {
    List<List<String>> res=new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard=new char[n][n];
        for(char[] c:chessboard){
            Arrays.fill(c, '.');
        }
        dfs(n,0,chessboard);
        return res;
    }

    public void dfs(int n,int row,char[][] chessboard){
        if(row==n){
            res.add(Array2List(chessboard));
            return;
        }
        for(int col=0;col<n;col++){
            if(isValid(row,col,n,chessboard)){
                chessboard[row][col]='Q';
                dfs(n, row+1, chessboard);
                chessboard[row][col]='.';
            }
        }
        
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        //检查列
        for(int i=0;i<row;i++){
            if(chessboard[i][col]=='Q'){
                return false;
            }
        }
        //检查45度斜线
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chessboard[i][j]=='Q'){
                return false;
            }
        }

        //检查135度斜线
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
        if(chessboard[i][j]=='Q'){
            return false;
        }
    }
        return true;
    }

    private List Array2List(char[][] chessboard) {
        List<String> list=new ArrayList<>();
        for(char[] c:chessboard){
            list.add(String.valueOf(c));
        }
        return list;
    }

    
}
// @lc code=end

